package code.class3;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/heaters/description/
 * 供暖器问题
 * 解题思路：
 * 利用双指针判断最短供暖半径
 */
public class Code08_homeHeaters {
    public static void main(String[] args) {
        int[] house = {1, 5, 10, 15};
        int[] heaters = {3, 8, 12};
        int minRadius = findMinRadius(house, heaters);
        System.out.println("minRadius = " + minRadius);
    }

    public static int findMinRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int ans = 0, l = 0, r = 0;
        while (l < houses.length) {
            // 1.当房屋寻找到最优供暖时，跳到下一个房屋
            // 2.如果不是最优供暖方案，跳到下一个供暖器
            while (!best(houses, heaters, l, r)) {
                r++; // 供暖器向右移动
            }
            // 计算最小半径之后
            ans = Math.max(ans, Math.abs(heaters[r] - houses[l]));
            // 移到下一个房间
            l++;
        }
        return ans;
    }

    /**
     * 最优路径：
     * 情况 1：如果 r 已经是最后一个供暖器
     * 如果 r 已经是最后一个供暖器, r == heaters.length - 1 这个判断确保 r 不会超过最后一个供暖器。
     * <p>
     * 情况 2：如果 r 不是最后一个供暖器
     * 会检查当前供暖器 heaters[r] 是否比下一个供暖器 heaters[r+1] 更接近 houses[l]
     */
    // 当前的地点houses[i]由heaters[j]来供暖是最优的吗?
    // 当前地点houses[i]由heaters[j]来供暖，产生的半径a
    // 当前地点houses[i]由heaters[j+1]来供暖，产生的半径b
    // 如果a < b,说明最优，供暖不应该跳到下一个位置
    // 如果a >=b,则不是最优，供暖器应该跳到下一个位置
    public static boolean best(int[] house, int[] heaters, int l, int r) {
        return r == heaters.length - 1 ||
                Math.abs(heaters[r] - house[l]) < Math.abs(heaters[r + 1] - house[l]);
    }
}
